Data protection is a critical issue in mass storage systems, especially high-end data storage systems meant to handle mission critical data. One way to protect data in a storage system is by maintaining a mirror copy of all data stored in the system. However, because of the high cost of such a level of protection, alternate protection schemes have been developed in the art. These approaches are usually classified as various levels of RAID (Redundant Array of Independent Disks). RAID levels were first defined in an article by Patterson, et. al, “A Case for Redundant Arrays of Inexpensive Disks,” University of Berkeley (1988). Enhancements to these levels are described in “The RAIDbook, A Source Book For Disk Array Technology,” Paul Massiglia, The RAID Advisory Board (6th Ed., 1999). In general, the RAID storage schemes utilize multiple storage devices so as to provide a means for protecting data while also balancing the load on the storage devices.
The RAID 5 scheme is generally considered a cost-effective method for protecting data while balancing the device load. Under the RAID 5 scheme, N disk drives form a RAID storage unit, where N is a positive integer. Data is grouped into sequences of (N−1) blocks, or portions, of data, and a corresponding parity block is calculated by XOR-ing the (N−1) data blocks. The (N−1) related data blocks and the corresponding parity block are distributed across the N drives as a group in such a manner that each block is stored on a different disk. Furthermore, parity blocks are not concentrated on one drive, but are evenly distributed among the drives, so that no single drive becomes a potential bottleneck.
The minimum number of disk drives in a RAID 5 storage unit is three, but it is common to use five or more drives. RAID 5 implementations provide balanced data storage and protection against single disk failure at a much lower cost than the scheme of mirroring all data. Whereas mirroring all data requires doubling the storage capacity, RAID 5 commonly requires an increase of 20% or less (corresponding to N equal to 5 or more) in the storage capacity.
A drawback to RAID 5 implementations is that they are only partly scalable, since a RAID 5 implementation comprising four disks may only increase its capacity by adding another four disks.
An article titled “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web,” by Karger et al., in the Proceedings of the 29th ACM Symposium on Theory of Computing, pages 654-663, (May 1997), whose disclosure is incorporated herein by reference, describes a technique of consistent hashing, and the use of a consistent hashing function. Such a function allocates objects to devices so as to spread the objects evenly over the devices, so that there is a minimal redistribution of objects if there is a change in the devices, and so that the allocation is consistent, i.e., is reproducible. The article applies a consistent hashing function to read-only cache systems, i.e., systems where a client may only read data from the cache system, not write data to the system, in order to distribute input/output requests to the systems.
An article titled “Differentiated Object Placement and Location for Self-Organizing Storage Clusters,” by Tang et al., in Technical Report 2002-32 of the University of California, Santa Barbara (November, 2002), whose disclosure is incorporated herein by reference, describes a protocol for managing a storage system where components are added or removed from the system. The protocol uses a consistent hashing scheme for placement of small objects in the system.
U.S. Pat. No. 6,484,269 to Kopylovitz, whose disclosure is incorporated herein by reference, describes a data storage system for receiving data to be stored on at least one data storage device. The data storage system comprises a central controller and a plurality of data storage devices connected to the central controller, each device including a data integrity value generator and a data storage element.